import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 这是 LeetCode 15. 三数之和 的解决方案
 * https://leetcode.cn/problems/3sum
 */
class ThreeSum {
    /**
     * 方法： threeSum
     *
     * 逻辑: 在给定的整数数组中找到所有不重复的三元组，使它们的和为零。
     *
     * Args:
     *   nums (int[]): 输入的整数数组。
     *
     * Returns:
     *   List<List<Integer>>: 包含所有满足条件的三元组的列表。
     *
     * Time:  
     *   O(N^2)，其中 N 是数组的长度。排序操作为 O(N log N)，双指针遍历为 O(N^2)。
     *
     * Space:  
     *   O(1)，除了返回值外，只使用常数级别的额外空间。
     */
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> ans = new ArrayList<>();
        int n = nums.length;
        for(int i = 0; i< n - 2; i++){
            int x = nums[i];
            if(i > 0 && x == nums[i - 1]) continue; //跳过重复数字
            if(x + nums[i+1] + nums[i+2] > 0) break; //优化，连续三个数相加大于0跳出
            if(x + nums[n-2] + nums[n-1] < 0) continue; //优化二，相加小于0，向后循环
            int j = i + 1;
            int k = n - 1;
            while(j < k){
                int s = x + nums[j] + nums[k];
                if (s > 0) {
                    k--;
                } else if(s < 0){
                    j++;
                } else{
                    ans.add(Arrays.asList(x, nums[j], nums[k]));
                    //跳过重复数字
                    for(j++; j < k && nums[j] == nums[j - 1]; j++);
                    for(k--; k > j && nums[k] == nums[k + 1]; k--);
                }
            }
        }
        return ans;
    }
}